package 树;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;

/**
 * 
 * @author ：soulstones
 * @version ：2019年9月25日 下午10:28:34 @Description：
 * 
 * 
 */
public class 创建树 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		// <parent ,childList>
		LinkedHashMap<Integer, List<Integer>> datas = new LinkedHashMap<Integer, List<Integer>>();
		while (scanner.hasNext()) {
			int edges = scanner.nextInt();
			// 将树的信息保存到hashMap<parent ,childList>中
			for (int i = 0; i < edges; i++) {
				int parent = scanner.nextInt();
				int child = scanner.nextInt();
				if (!datas.containsKey(parent)) {
					List<Integer> childs = new ArrayList<Integer>();
					childs.add(child);
					datas.put(parent, childs);
				} else {
					List<Integer> childs = datas.get(parent);
					childs.add(child);
				}
			}

			BinaryNode root = buildTree(datas);
			int heigh = height(root);
			
			//输出二叉树的高度
			System.out.println(heigh);
		}
		scanner.close();
	}

	// 求二叉树的高度，这里使用递归方式
	private static int height(BinaryNode root) {
		if (root == null) {
			return 0;
		}
		int leftHight = height(root.left);
		int rightHeight = height(root.right);

		return 1 + (leftHight > rightHeight ? leftHight : rightHeight);
	}

	// 二叉树的高度，这里使用非递归的方法
	// 求每层的个数，树的最大宽度，都可以采用这种思想
	static int height1(BinaryNode root) {
		int front = -1, rear = -1;
		int last = 0, level = 0;
		BinaryNode[] queue = new BinaryNode[10000];
		if (root == null) {
			return 0;
		}
		queue[++rear] = root;
		BinaryNode p;
		while (front < rear) {
			p = queue[++front];
			if (p.left != null) {
				queue[++rear] = p.left;
			}
			if (p.right != null) {
				queue[++rear] = p.right;
			}
			if (front == last) {
				level++;
				last = rear;
			}
		}
		return level;
	}

	// 构造二叉树
	public static BinaryNode buildTree(Map<Integer, List<Integer>> datas) {

		BinaryNode root = null;
		BinaryNode current = null;
		List<Integer> childs = null;

		Set<Entry<Integer, List<Integer>>> entrySet = datas.entrySet();
		for (Map.Entry<Integer, List<Integer>> entry : entrySet) {
			int parent = entry.getKey();
			current = findNode(parent, root);
			childs = datas.get(parent);
			if (current == null) { // 说明parent 是根节点
				root = new BinaryNode(parent);
				createNode(root, childs);
			} else {
				createNode(current, childs);
			}
		}
		return root;
	}

	// 创建parent节点的左右孩子节点
	private static void createNode(BinaryNode parent, List<Integer> childs) {
		if (childs.size() == 2) { // 说明存在左右孩子
			BinaryNode leftChild = new BinaryNode(childs.get(0));
			BinaryNode rightChild = new BinaryNode(childs.get(1));
			parent.left = leftChild;
			parent.right = rightChild;
		}
		if (childs.size() == 1) { // 说明只有左孩子
			BinaryNode leftChild = new BinaryNode(childs.get(0));
			parent.left = leftChild;
		}
	}

	// 查找树根为root的二叉树中，值为nodeVal的节点
	private static BinaryNode findNode(int nodeVal, BinaryNode root) {
		// 先序递归遍历查找，值为nodeVal的节点
		BinaryNode target = null;

		if (root == null) {
			return null;
		}
		if (root.val == nodeVal)
			return root;
		target = findNode(nodeVal, root.left); // 先在左子树中查找

		if (target == null)
			target = findNode(nodeVal, root.right); // 左子树中未找到，则在右子树中查找
		return target;
	}

	private static class BinaryNode {
		int val;
		BinaryNode left;
		BinaryNode right;

		public BinaryNode(int val) {
			this.val = val;
			left = right = null;
		}
	}

}
